1108F - MST Unification - CodeForces Solution

// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
typedef long long ll;
#define pb push_back
#define ff first
#define ss second
#define INF 6223372004895760000
#define NIL 0
#define int ll
// #define ll int
#define debug cout << "here\n";
using vll=vector<ll>;
using vi=vector<int>;
using vpl = vector<pair<ll, ll>>;
using pll = pair<ll, ll>;
ll mod = 1000000007;
ll mod2 = 998244353;
ll MOD = mod2;
ll tcnt = 1;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
// #define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
const int MAXN = 200005;
ll ipow(ll base, ll k, ll M) {
    base %= M;
    k = k % (M - 1);
    ll total = 1;
    while(k) {
        if(k & 1) {
            total = (total * base) % M;
        }
        base = (base * base) % M;
        k >>= 1;
    }
    return total;
}

ll modu(ll a,ll b) {
  ll c = a % b;
  return (c < 0) ? c + b : c;
}
inline uint64_t modpow(uint64_t base, uint64_t exp, uint64_t modulus) {
    base %= modulus;
    uint64_t result = 1;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % modulus;
        base = (base * base) % modulus;
        exp >>= 1;
    }
    return result;
}
 
inline uint64_t modinv(uint64_t x, uint64_t mod) {
    return modpow(x, mod - 2, mod);
}
 
uint64_t fak[MAXN];
 
void precomp() {
    fak[0] = fak[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        fak[i] = i*fak[i - 1];
        fak[i] %= MOD;
    }
}
 
inline uint64_t nCr(uint64_t n, uint64_t r) {
    uint64_t res = fak[n] * modinv(fak[r], MOD);
    res %= MOD; 
    res *= modinv(fak[n - r], MOD);
    res %= MOD;
    return res;
}

ll intlen(ll n) {
    ll cnt = 0;
    while(n) {
        n /= 10;
        cnt++;
    }
    return cnt;
}

ll parent[MAXN];

void make_set(int v) {
    parent[v] = v;
}
 
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}
 
void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b)
        parent[b] = a;
}

void solve(){
    ll n,m;
    cin >> n >> m;
    vector<vll> v;
    map<ll, vpl> mp;
    for(ll i=0; i<m; i++){
        ll a,b,c;
        cin >> a >> b >> c;
        v.pb({c, a - 1, b - 1});
        mp[c].pb({a - 1, b - 1});
    }
    for(ll i=0; i<n; i++){
        make_set(i);
    }
    ll ans = 0;
    sort(v.begin(), v.end());
    for(auto &x: mp){
        ll temp = 0;
        for(auto &y: x.ss){
            if(find_set(y.ff) == find_set(y.ss)){
                temp--;
            }
        }
        for(auto &y: x.ss){
            if(find_set(y.ff) == find_set(y.ss)){
                temp++;
            }
            else{
                union_sets(y.ff, y.ss);
            }
        }
        ans += temp;
    }
    cout << ans << "\n";
}

signed main(){
    // precomp();
    fast
    // #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif
    ll tc = 1, cnt = 1;
    // cout << setprecision(20);
    // cin >> tc;
    while(tc--){
        // cout << "Case #" << cnt++ << ": ";
        solve();
        tcnt++;
    }
}